#-*- coding: utf-8 -*-

import time
import sys

'''

 autor: António Delgado
 Data: 11-03-2013


'''
'''ordernar elementos do array'''
class Insertion_Sort:
    
    def __init__(self, A):
        self.A = A
        
    def Insertion_Sort(self, A):
        for j in xrange(1, len(self.A)):
            key = self.A[j]
            i = j - 1
            while i > -1 and self.A[i] > key:
                self.A[i+1] = self.A[i]
                i = i-1
                pass
            self.A[i+1] = key
        return A


'''impresão e tempo de execução'''
A = [5, 2, 4, 6, 1, 3]
execucaoOne= time.clock()
print 'Desordenado:', A
I = Insertion_Sort(A)
execucaoTwo= time.clock()
print 'Ordenado:', I.Insertion_Sort(A)
print 'Time Inicial:', execucaoOne
print 'Time final:', execucaoTwo
print 'Time Final-Inicial:', execucaoTwo-execucaoOne

from random import uniform
from time import clock

Z = [1] + range(50, 1050, 50)
T = []
M = 25
for n in Z:
    A = [ uniform(0.0,1.0) for k in xrange(n)]
    tempos = []
    for k in range(M):
        t1 = clock()
        Insertion_Sort(A)
        t2 = clock()
        tempos.append(t2-t1)
    media = reduce(lambda x, y: x + y, tempos) / len(tempos)
    var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
    
    T.append((n,media, var))

X = [n for n, media, var in T]
Y = [media for n, media, var in T]
ct=15e6
Z = [n**2/ct for n, media, var in T]

import matplotlib.pyplot as plt
plt.grid(True)
plt.ylabel(u'T(n) - tempo de execução médio em segundos')
plt.xlabel(u'n - número de elementos')
plt.plot(X,Y,'rs', label="resultado experimental")
plt.plot(X, Z, 'b^', label=u"previsão teórica")
plt.legend()
plt.show()

